The present invention relates to a method for increasing the security of public key encryption algorithms. An encryption schema comprises an encryption algorithm and a decryption algorithm each having a particular encryption and decryption method.
In the conventional secret key cryptography model, two people wishing to communicate by means of a non-secure channel must first agree upon a secret encryption key K. The encryption function and the decryption function use the same key K. The drawback of the secret key encryption system is that said system requires prior communication of the key K between the two people by means of a secure channel, before any encrypted message is sent across the non-secure channel. In practice, it is generally difficult to find a perfectly secure communication channel, especially if the distance separating the two people is large. Secure channel means a channel for which it is impossible to know or modify the information passing through said channel. Such a secure channel can be implemented by a cable connecting two terminals, owned by said two people.
The concept of public key cryptography was invented by Whitfield Diffie and Martin Hellman in 1976. Public key cryptography makes it possible to solve the problem of distribution of keys across a non-secure channel. The principle of public key cryptography consists of using a pair of keys, a public encryption key and a private decryption key. It must be computationally impracticable to find the private decryption key from the public encryption key. A person A wishing to communicate information to a person B uses the public encryption key of person B. Only person B possesses the private key associated with their public key. Only person B is therefore capable of decrypting the message sent to them.
Another advantage of public key cryptography over secret key cryptography is that public key cryptography allows authentication through the use of electronic signing.
The first public key encryption schema implementation was devised in 1977 by Rivest, Shamir and Adleman, who invented the RSA encryption system. The security of RSA is based on the difficulty of factorising a large number which is the product of two prime numbers. Since then, numerous public key encryption systems have been proposed, the security of which is based on different computational problems (this list is not exhaustive):                Merkle-Hellman knapsack:        
This encryption system is based on the difficulty of the subset sum problem.                McEliece:        
This encryption system is based on algebraic code theory. It is based on the linear code decoding problem.                El-Gamal:        
This encryption system is based on the difficulty of the discrete logarithm in a finite field.                Elliptical curves:        
The elliptical curve encryption system constitutes a modification of existing cryptographic systems in order to apply them to the field of elliptical curves. The advantage of elliptical curve encryption systems is that they require a smaller key size than for the other encryption systems.
In the following, it is understood that all the elements necessary for the encryption schema of the invention, like for example the message M, the encrypted item C and all the abbreviations of letters or letters and numerals which follow in the description below, are integer numbers equivalent to bit strings. For example, the symbol a∥b denotes the concatenation of the binary representations of the integers a and b, which are in fact the respective bit strings of a and b.
A deterministic encryption algorithm takes at the input the message M to be encrypted and returns at the output the encrypted message C.
Furthermore, a probabilistic encryption algorithm usually takes at the input the message M to be encrypted and a random number u, and returns at the output an encrypted message C, using the public key of the recipient. The decryption algorithm takes at the input the encrypted item C and returns at the output the message M, using the private key. One example of a public key probabilistic encryption algorithm is the El-Gamal encryption algorithm.
However, the majority of public key probabilistic encryption algorithms do not in themselves have a sufficient level of security. This is because there are numerous practical situations in which an attacker can have access to a data processing machine implementing the decryption algorithm using the private key. If the attacker possesses an encrypted message C, they can thus request the decryption machine to decrypt certain well-chosen encrypted messages C′, different from the encrypted message C, and thus obtain information on the message M corresponding to the encrypted message C.